package array.leetcode.medium;

/**
 * @author bruin_du
 * @description 二维子矩阵的和
 * @date 2022/8/4 16:09
 **/
public class OfferII013_SumRegion {
    int[][] res;
    public OfferII013_SumRegion(int[][] matrix) {
        int rowLen = matrix.length, colLen = matrix[0].length;
        int[][] pre = new int[rowLen + 1][colLen + 1];
        for (int i = 1; i <= rowLen; i++) {
            for (int j = 1; j <= colLen; j++) {
                pre[i][j] = pre[i][j - 1] + pre[i - 1][j]  + matrix[i - 1][j - 1] - pre[i - 1][j - 1];
            }
        }
        res = pre;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return res[row2 + 1][col2 + 1] + res[row1][col1] - res[row2 + 1][col1] - res[row1][col2 + 1];
    }
}
